In digital image processing applications, image restoration is usually used for restoring an original image from a blurred and noisy observed image where prior knowledge of the system point spread function (PSF) or blurring function is available. Image restoration can be applied to numerous applications including astronomy, medical imaging, military surveillance, and digital television (DTV).
The conventional one dimensional image restoration based on “regularized least square” requires the calculation of fast Fourier transform (FFT) of the observed image and the system PSF. Then, complex divisions and multiplications between the FFTs of the observed image and the system PSF are performed in frequency domain and the result is further processed by inverse FFT (IFFT) to obtain the restored image in spatial domain.
A discrete model for a 1-D linear shift invariant (LSI) image acquisition (including degradations caused by a PSF and additive noise) can be given by defined as:
                                          g            ⁡                          [              n              ]                                =                                                                      ∑                                      k                    =                    0                                                        N                    -                    1                                                  ⁢                                                      h                    ⁡                                          [                                              n                        -                        k                                            ]                                                        ⁢                                      f                    ⁡                                          [                      n                      ]                                                                                  +                                                v                  ⁡                                      [                    n                    ]                                                  ⁢                                                                  ⁢                for                ⁢                                                                  ⁢                n                                      =            0                          ,        1        ,        2        ,        …        ⁢                                  ,                  N          -          1                ,                            (        1        )            
wherein g[n] is a degraded (blurred and noisy) observed image of length N, f[n] represents an original image, h[n] is the system PSF (assumed to be known), and v[n] is an additive noise introduced by system. Let H(u) and G(u) denote the FFTs of the system PSF and observed image, respectively. The restored image R(u) in the frequency domain based on regularized least square can be expressed as:
                                          R            ⁡                          (              u              )                                =                                                    [                                                                            H                      *                                        ⁡                                          (                      u                      )                                                                                                                                                    H                          *                                                ⁡                                                  (                          u                          )                                                                    ⁢                                              H                        ⁡                                                  (                          u                          )                                                                                      +                    γ                                                  ]                            ⁢                              G                ⁡                                  (                  u                  )                                            ⁢                                                          ⁢              for              ⁢                                                          ⁢              u                        =            0                          ,        1        ,        …        ⁢                                  ,                  N          -          1.                                    (        2        )            
The superscript * in the preceding equation is the complex conjugate operator and constant γ is commonly referred to as the regularization parameter, which helps control the tradeoff between fidelity of the observed data and the smoothness of the solution. The restored image in spatial domain r[n] can be calculated using the IFFT of the result in relation (2) above.
It is known that the highest complexity of this conventional image restoration is due to the calculation of FFT and its inverse counterpart of the same length N as the observed image. In practice, the implementation of FFT of the same length as the observed image is complicated and difficult in hardware design. Further, generally the image length N is not a power of 2. Therefore, calculation of FFT of such length generally cannot be performed in an efficient manner.